删除链表的倒数第 N 个结点

题目链接 · 灵神原题解（署名来源）

想象有一把长度固定的尺子，左端点在链表头部，右端点在正数第 $n$ 个节点。向右移动尺子，当尺子右端点到达链表末尾时，左端点就在倒数第 $n$ 个节点。

由于需要删除节点，我们需要找倒数第 $n$ 个节点的前一个节点（倒数第 $n + 1$ 个节点），这样才能做删除操作。

修改：左端点在链表头部，右端点在正数第 $n + 1$ 个节点。向右移动尺子，当尺子右端点到达链表末尾时，左端点就在倒数第 $n + 1$ 个节点。

细节：如果 $n$ 等于链表长度呢？没有正数第 $n + 1$ 个节点。难道要特判这种情况？

不需要。我们可以在头节点的前面插入一个哨兵节点（dummy node），把它当作链表的头节点，这样就有正数第 $n + 1$ 个节点了。换句话说，如果遇到需要删除头节点的题目，添加哨兵节点可以简化代码逻辑，请记住这个技巧。

具体请看视频讲解：【基础算法精讲 08】，制作不易，欢迎点赞关注~

答疑

问：前后指针的做法为什么算作「一次遍历」？链表节点不是会被遍历两次吗？这个算法的优点是什么？

答：链表节点是会被遍历两次。其实我觉得这题本质上想考察的是，在不知道链表长度的前提下，设计一个算法，在「到达链表末尾的瞬间」就能知道倒数第 $n$ 个节点。这个算法的优点是，当 $n$ 比较小，且链表节点分配具有一定局部性时，前后指针的做法 cache miss 更少（相比一个指针跑两趟的算法）。

问：一般在做链表题时，什么时候要写 while node，什么时候要写 while node.next？

答：如果要遍历到最后一个节点，需要写 while node；如果要遍历到倒数第二个节点，需要写 while node.next。

Python 解法1C++ 解法1

python

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # 由于可能会删除链表头部，用哨兵节点简化代码
        left = right = dummy = ListNode(next=head)
        for _ in range(n):
            right = right.next  # 右指针先向右走 n 步
        while right.next:
            left = left.next
            right = right.next  # 左右指针一起走
        left.next = left.next.next  # 左指针的下一个节点就是倒数第 n 个节点
        return dummy.next

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 由于可能会删除链表头部，用哨兵节点简化代码
        ListNode dummy{0, head};
        ListNode* left = &dummy;
        ListNode* right = &dummy;
        while (n--) {
            right = right->next; // 右指针先向右走 n 步
        }
        while (right->next) {
            left = left->next;
            right = right->next; // 左右指针一起走
        }
        // 左指针的下一个节点就是倒数第 n 个节点
        ListNode* nxt = left->next;
        left->next = left->next->next;
        delete nxt;
        return dummy.next;
    }
};

复杂度分析

时间复杂度： $O (m)$ ，其中 $m$ 是链表的长度。
空间复杂度： $O (1)$ 。

专题训练

见下面链表题单的「§1.5 前后指针」。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

答疑 ​

复杂度分析 ​

专题训练 ​

分类题单 ​

答疑

复杂度分析

专题训练

分类题单